package sort;

public class Helan_flag {
    public static void main(String[] args) {
        int[] arr={3,7,6,2,0,5,3,4,9};
        for (int x:arr){
            System.out.print(x+" ");
        }
        sort1(arr,4);
        for (int x:arr){
            System.out.print(x+" ");
        }
    }

    /*
    * 将数组分成大于n和小于等于n的两个部分 要求时间复杂度O(n)  额外空间复杂度O(1)
    * */
    public static void sort1(int[] arr,int n){
        int p=-1;   //定义小于等于区指针
        int eq=-1;   //定义等于区指针
        for (int a=0;a<arr.length;a++){
            if (arr[a]<=n){
                swap(arr,p+1,a);
                p++;
            }
        }

    }
    public static void swap(int[] arr,int a,int b){
        int temp=arr[a];
        arr[a]=arr[b];
        arr[b]=temp;
    }
}
